package class5;

import common.TreeNode;
import common.TreeNodeUtils;

import java.util.*;

/**
 * 二叉树的层序遍历
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 * root结构:
 * +        1
 * +      /   \
 * +     2      3
 * +      \    /  \
 * +      4   5    6
 * +     / \   \    \
 * +    7   8   9    10
 * +     \ /
 * +    11 12
 */
public class Code06_LevelOrderBottom {
    public static void main(String[] args) {
        TreeNode root = getTreeNode();
        List<List<Integer>> levelOrder = getLevelOrder(root);
        System.out.println("levelOrder = " + levelOrder);

    }

    public static List<List<Integer>> getLevelOrder(TreeNode root) {
        LinkedList<List<Integer>> ans = new LinkedList<>();
        if (root == null) return ans;
        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> curArrs = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                curArrs.add(cur.val);
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            ans.add(curArrs);
        }
        return ans;

    }

    private static TreeNode getTreeNode() {
        TreeNode root = TreeNodeUtils.createTreeNode(1, 2, 3);
        TreeNode[] thr = TreeNodeUtils.getTreeNodes(4, 5, 6);
        TreeNode[] foth = TreeNodeUtils.getTreeNodes(7, 8, 9, 10);
        TreeNode[] fiv = TreeNodeUtils.getTreeNodes(11, 12);

        foth[2].right = fiv[0];
        foth[3].left = fiv[1];

        thr[0].left = foth[0];
        thr[0].right = foth[1];

        thr[1].right = foth[2];
        thr[2].right = foth[3];

        root.left.right = thr[0];
        root.right.left = thr[1];
        root.right.right = thr[2];
        return root;
    }
}
